﻿// 10213. 「一本通 6.4 例 5」Strange Way to Express Integers.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>


using namespace std;

/*
https://loj.ac/p/10213

题目描述
原题来自：POJ 2891

给定 2n 个正整数 a_1,a_2,... ,a_n 和 m_1,m_2,... ,m_n，求一个最小的正整数 x，满足 forall i in[1,n], x =- a_i (mod m_i)，或者给出无解。

输入格式
多组数据。

每组数据第一行一个整数 n；
接下来 n 行，每行两个整数 m_i,a_i。

输出格式
对于每组数据，若无解，输出 -1；否则输出一个非负整数，若有多解，输出最小的满足条件的答案。

2
8 7
11 9


31

数据范围与提示
对于全部数据，所有的输入都是非负的，并且可以用 64 位有符号整数表示。保证 1<= n<= 10^5,m_i >= a_i。
*/


// 204. 表达整数的奇怪方式.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//



typedef long long  LL;

LL exgcd(LL a, LL b, LL& x, LL& y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}

	LL d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}


int main()
{
	int n;
	while (cin >> n){
		LL x = 0, a1, m1;
		cin >> a1 >> m1;
		int j;
		for (int i = 0; i < n - 1; i++) {
			j = i;
			LL a2, m2;
			cin >> a2 >> m2;
			LL k1, k2;
			LL d = exgcd(a1, a2, k1, k2);
			if ((m2 - m1) % d) {
				x = -1;
				break;
			}

			k1 *= (m2 - m1) / d;
			k1 = (k1 % (a2 / d) + a2 / d) % (a2 / d);

			x = k1 * a1 + m1;

			LL m = (a1 / d * a2);
			m1 = x;
			a1 = m;
		}
		if (x == -1) {
			cout << -1 << endl;
			int t1, t2;
			j = j + 1;
			for (; j < n - 1; j++) {
				cin >> t1 >> t2;
			};
			//条件不符合   进行下一轮
			continue;
		}

		if (x != -1) x = (m1 % a1 + a1) % a1;

		cout << x << endl;
	}


	return 0;
}




 